/**
//设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。 
//
// 示例： 
//
// 输入： arr = [1,3,5,7,2,4,6,8], k = 4
//输出： [1,2,3,4]
// 
//
// 提示： 
//
// 
// 0 <= len(arr) <= 100000 
// 0 <= k <= min(100000, len(arr)) 
// 
// Related Topics 数组 分治 快速选择 排序 堆（优先队列） 👍 185 👎 0

*/

package com.xixi.basicAlgroithms.sort;
public class ID_interview_17_14_SmallestKLcci {
public static void main(String[] args) {
Solution solution = new ID_interview_17_14_SmallestKLcci().new Solution();
}


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] smallestK(int[] arr, int k) {

        quickSort(arr, 0, arr.length -1);

        int[] result = new int[k];
        for(int i = 0; i < k; ++i){
            result[i] = arr[i];

        }

        return  result;
    }


    public void quickSort(int[] arr, int start, int pivot){
        if(start >= pivot){
            return;
        }

        int pivotValue = arr[pivot];

        int nextPivot = start;
        for(int i = start; i < pivot; i++){
            if(arr[i] < pivotValue){
                swap(arr,i, nextPivot);
                nextPivot++;
            }

        }

        swap(arr, nextPivot,pivot);
        quickSort(arr, start, nextPivot - 1);
        quickSort(arr, nextPivot + 1, pivot);

    }
    public void swap(int[] arr, int a, int b){
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;

    }

}
//leetcode submit region end(Prohibit modification and deletion)




}